#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include "Stack.h"
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include "cal.h"

int Judge(char character)
{
	int flag = 0;
	if (character == '+')
		flag = 1;
	else if (character == '-')
		flag = 2;
	else if (character == '*')
		flag = 3;
	else if (character == '/')
		flag = 4;
	else if (character == '(')
		flag = 5;
	else if (character == ')')
		flag = 6;
	else if (character == '=')
		flag = 7;

	return flag;
}

int GetValue(char thetha, int a, int b) {
	switch (thetha) {
	case '+':
		return a + b;
		break;
	case '-':
		return a - b;
		break;
	case '*':
		return a * b;
		break;
	case '/':
		return int(a / b);
		break;
	}
}

BiTree* ExpTree_Init(OPTR* optr_stack, stack_BiTree* bitree_stack,int* num)
{
	char str[100] = { 0 };
	int j = 0;
	BiTree* forest = (BiTree*)malloc(sizeof(BiTree) * MAX_INPUT);
	for (j = 0; j < MAX_INPUT; j++)
	{
		forest[j] = (BiTree)malloc(sizeof(BiTreeNode) * MAX_INPUT);
	}
	while (1)
	{
		scanf("%s", str);
		if (str[0] == '=')//如果输入是=，直接结束函数
		{
			return forest;
		}
		else
		{
			int i = 0;
			for (i = 0; i < strlen(str); i++)
			{
				if ((str[i] == '=' && optr_stack->element[optr_stack->top] != ')' ) || optr_stack->element[optr_stack->top] == '=')
				{
					while (optr_stack->element[optr_stack->top] != '#')
					{
						//由于我是创建的栈的数组，并且每次pop都是返回这次弹出的数组元素的地址，所以本质上栈里的元素没有变化，需要创建新的相同类型的元素，从而避免在后面创建新的树和栈元素时发生相互干扰
						char thetha = Stack_Pop_OPTR(optr_stack);
						BiTree poptree1 = Stack_Pop_BiTree(bitree_stack);
						BiTree poptree2 = Stack_Pop_BiTree(bitree_stack);
						BiTree gettree1 = (BiTree)malloc(sizeof(BiTreeNode));
						BiTree gettree2 = (BiTree)malloc(sizeof(BiTreeNode));
						gettree1->data = poptree1->data;
						gettree1->leftChild = poptree1->leftChild;
						gettree1->rightChild = poptree1->rightChild;
						gettree2->data = poptree2->data;
						gettree2->leftChild = poptree2->leftChild;
						gettree2->rightChild = poptree2->rightChild;
						BiTree nowget = ExpTree_Create(gettree1, gettree2, thetha);
						Stack_Push_BiTree(bitree_stack, *nowget);
					}
					break;
				}
				if (Judge(str[i]) == 0)//该字符是数字
				{
					BiTree nowget = ExpTree_Create(NULL, NULL, str[i]);
					Stack_Push_BiTree(bitree_stack,*nowget);
				}
				else
				{
					char priority = getPriority(optr_stack->element[optr_stack->top], str[i]);
					if (priority == '<')
					{
						Stack_Push_OPTR(optr_stack,str[i]);
					}
					else if (priority == '>')
					{
						if (optr_stack->element[optr_stack->top] != ')')
						{
							char thetha = Stack_Pop_OPTR(optr_stack);
							BiTree poptree1 = Stack_Pop_BiTree(bitree_stack);
							BiTree poptree2 = Stack_Pop_BiTree(bitree_stack);
							BiTree gettree1 = (BiTree)malloc(sizeof(BiTreeNode));
							BiTree gettree2 = (BiTree)malloc(sizeof(BiTreeNode));
							gettree1->data = poptree1->data;
							gettree1->leftChild = poptree1->leftChild;
							gettree1->rightChild = poptree1->rightChild;
							gettree2->data = poptree2->data;
							gettree2->leftChild = poptree2->leftChild;
							gettree2->rightChild = poptree2->rightChild;
							BiTree nowget = ExpTree_Create(gettree1, gettree2, thetha);
							Stack_Push_BiTree(bitree_stack, *nowget);
							Stack_Push_OPTR(optr_stack, str[i]);
						}
						else
						{
							Stack_Pop_OPTR(optr_stack); //弹出此时的栈顶 ）
							while (optr_stack->element[optr_stack->top] != '(')
							{
								char thetha = Stack_Pop_OPTR(optr_stack);
								BiTree poptree1 = Stack_Pop_BiTree(bitree_stack);
								BiTree poptree2 = Stack_Pop_BiTree(bitree_stack);
								BiTree gettree1 = (BiTree)malloc(sizeof(BiTreeNode));
								BiTree gettree2 = (BiTree)malloc(sizeof(BiTreeNode));
								gettree1->data = poptree1->data;
								gettree1->leftChild = poptree1->leftChild;
								gettree1->rightChild = poptree1->rightChild;
								gettree2->data = poptree2->data;
								gettree2->leftChild = poptree2->leftChild;
								gettree2->rightChild = poptree2->rightChild;
								BiTree nowget = ExpTree_Create(gettree1, gettree2, thetha);
								Stack_Push_BiTree(bitree_stack, *nowget);
							}
							if (str[i] != '=')
							{
								Stack_Pop_OPTR(optr_stack); //弹出此时的栈顶 (
								//Stack_Push_OPTR(optr_stack, str[i]);//压入括号后面的操作符
								i--;
							}
							else
							{
								Stack_Pop_OPTR(optr_stack); //弹出此时的栈顶 (
								i--;
							}
						}
					}
					else if (priority == '=')
					{
						Stack_Pop_OPTR(optr_stack);//栈顶是一个(,把它弹出
					}
				}
			}
		}
		BiTree poptree = Stack_Pop_BiTree(bitree_stack);
		BiTree gettree = (BiTree)malloc(sizeof(BiTreeNode));
		gettree->data = poptree->data;
		gettree->leftChild = poptree->leftChild;
		gettree->rightChild = poptree->rightChild;
		forest[*num] = gettree;
		(*num)++;
	}
	return forest;
}

int EvaluateExpTree(BiTree T)
{
	int lvalue = 0;
	int rvalue = 0;
	if (T->leftChild == NULL && T->rightChild == NULL)
		return T->data - '0';
	else
	{
		lvalue = EvaluateExpTree(T->leftChild);
		rvalue = EvaluateExpTree(T->rightChild);
		return GetValue(T->data, rvalue, lvalue);
	}
}